package huisu.onClass.class01.exer04;

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    private static int minGroups = Integer.MAX_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] matrix = new int[n][n];
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int vex1 = sc.nextInt() - 1;
            int vex2 = sc.nextInt() - 1;
            matrix[vex1][vex2] = 1;
            matrix[vex2][vex1] = 1;
        }
        LinkedList<LinkedList<Integer>> allLists = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            allLists.add(new LinkedList<>());
        }
        dfs(allLists, 1, n, matrix);
        System.out.println(minGroups);
    }

    private static void dfs(LinkedList<LinkedList<Integer>> allLists, int curPerson, int n, int[][] matrix) {
        if (curPerson > n) {
            // cal
            int count = 0;
            for (int i = 0; i < allLists.size(); i++) {
                if (allLists.get(i).size() != 0) {
                    count++;
                }
            }
            minGroups = Math.min(minGroups, count);
            return;
        }
        for (int i = 0; i < allLists.size(); i++) {
            boolean canAdd = true;
            LinkedList<Integer> curList = allLists.get(i);
            for (int mem : curList) {
                if (matrix[mem - 1][curPerson - 1] == 1) {
                    canAdd = false;
                    break;
                }
            }
            if (canAdd) {
                curList.add(curPerson);
                dfs(allLists, curPerson + 1, n, matrix);
                curList.removeLast();
            }
        }
    }
}
